﻿// 0911train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 幼儿园组织活动，老师布置了一个任务: 每个小朋友去了解与自己同一个小区的小朋友还有几个
 我们将这些数量汇总到数组garden中，请根据这些小朋友给出的信息，计算班级小朋友至少来自几个小区？
输入
garden = [2, 2, 3]
说明:
garden数组长度最大为999。每个小区的小朋友数量最多1000人，也就是garden的范围为[0,999]
输出
一个数字

输入
2 2 3
输出
7
 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec)
    {
        //2个人反馈容量为3,2个人都属于3
        //ceil(people_count/(accept_num+1))
        unordered_map<int, int>accept_map;
        for (auto&num:num_vec)
        {
            //accept, people_count
            accept_map[num] += 1;
        }

        int result = 0;
        for (auto&map_item:accept_map)
        {
            double accept_num = map_item.first;
            double people_count = map_item.second;

            int item_count = ceil(people_count / (accept_num + 1)) * (accept_num + 1);
            result += item_count;
        }

        cout << result;

	    //Solution01
    }
};

/*
小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t
k，t，n都是给定的。求出可行解数量

输入描述
第一行输入 n t k，用空格进行分割
第二行输入 每个运动的卡路里 按照空格进行分割

输出描述
求出可行解数量

输入
4 3 2
1 1 2 3

输出
2

4 3 2 n(v_size) t(target_sum) k(limit)
 */
class Solution02
{
public:
    Solution02(vector<int>&kind_vec, int target_sum, int target_limit)
    {
        //for(auto&kind:kind_vec)
        //for(int sum=target_sum; sum>=0; sum--)
        //dp[sum][sum_l]+=dp[sum-kind][sum_l-1]
        vector<vector<int>>dynamic_v(target_sum + 1, vector<int>(target_limit +1));

        //凑到0,0种选择，1种方法
        dynamic_v[0][0] = 1;
        //dp[0][limit]=0

        for (auto&kind:kind_vec)
        {
            for (int sum=target_sum; sum>=0; sum--)
            {
                for (int limit=1; limit<=target_limit; limit++)
                {
                    if (sum - kind < 0)
                    {
                        continue;
                    }
                    dynamic_v[sum][limit] += dynamic_v[sum - kind][limit - 1];
                }
	            //for
            }
            //for
        }

        cout << dynamic_v[target_sum][target_limit];

        //Solution02
    }
};


/*
在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米
每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和
注意：除了第一个和最后一个路灯，第i个路灯的照明区域为[100*i-r, 100*i+r]，
即照明半径表示该路灯其前后区域都能照明。

输入描述
第一行为一个数N，表示路灯个数，1 <= N <= 100000
第二行为N个空格分隔的数，表示路灯的照明半径，1 <= 照明半径 <= 100000*100

输出描述
第一个路灯和最后一个路灯之间，无法照明的区间的长度和

输入
4
50 70 20 70
输出
20

路灯1 覆盖0-50，路灯2 覆盖30-170，路灯3覆盖180-220，路灯4覆盖230-370
没覆盖的区域是170-180和220-230，一共20米
 */
class Solution03
{
public:
    //第i个路灯的照明区域为[100*i-r, 100*i+r]
    Solution03(vector<int>& num_vec)
    {
        int v_size = num_vec.size();
        vector<vector<int>>cover_vec(v_size);

        vector<int>first_v = { 0, num_vec[0] };
        cover_vec[0] = first_v;

        for (int i = 1; i < v_size; i++)
        {
            int curr = num_vec[i];
            vector<int>curr_v = { 100 * i - curr, 100 * i + curr };

            //判断跟前面区间的关系
            //如果前面区间范围更大，选前面区间的
        	curr_v[1] = max(curr_v[1], cover_vec[i - 1][1]);
            cover_vec[i] = curr_v;
            //for
        }

        //反向扫一遍
        for (int i=v_size-2; i>=0; i--)
        {
            cover_vec[i][0] = min(cover_vec[i][0], cover_vec[i + 1][0]);
        }

        int result = 0;
        for (int i = 1; i < v_size; i++)
        {
            //180-220 [i][0]180
            //30-170 [i-1][1]170
            if (cover_vec[i][0]>cover_vec[i-1][1])
            {
                int diff_start = cover_vec[i - 1][1];
                int diff_end = cover_vec[i][0];
                result += (diff_end - diff_start);
            }
            //for
        }
        cout << result;
        //Solution03
    }
    //Solution03
};


/*
评估一个网络的信号质量，其中一个做法是将网络划分为栅格，
对每个栅格的信号质量计算，路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示，
现给出R行C列的整数数组COV，每个单元格的数值S即为该栅格的信号质量（已归一化，无单位，值越大信号越好）
要求从[0,0]到[R-1,C-1]设计一条最优路测路线。返回该路线得分。规则:
1. 路测路线可以上下左右四个方向，不能对角
2. 路线的评分是以路线上信号最差的栅格为准的，例如路径8->4->5->9的值为 4，该线路评分为4。线路最优表示该条线路的评分最高。

输入描述
第1行表示栅格的行数R
第2行表示栅格的列数C
第3行开始，每一行表示栅格地图一行的信号值，如5 4 5

输出描述
最优路线的得分

输入
3
3
5 4 5
1 2 6
7 4 6
输出
4

路线为5->4->5->6->6
 */
class Solution04
{
public:
    struct Node
    {
        int val, row, col;
        Node() = default;
        Node(int val, int row, int col) :val(val), row(row), col(col) {};

        bool operator<(const Node&other) const
        {
            return val < other.val;
        }
    };
    Solution04(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        vector<vector<bool>>checked(row_size, vector<bool>(col_size));

        priority_queue<Node>bfs_queue;
        Node first_node(grid[0][0], 0, 0);
        //标记已访问
        checked[0][0] = true;
        bfs_queue.push(first_node);

        bool is_find = false;
        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.top();
            bfs_queue.pop();

            //保存最小的信号
            result = min(result, top_node.val);

            for (auto&dir_vec:DirectionGrid)
            {
                int curr_r = top_node.row + dir_vec[0];
                int curr_c = top_node.col + dir_vec[1];

                if (curr_r==row_size-1 && curr_c==col_size-1)
                {
                    is_find = true;
                    result = min(result, grid[row_size - 1][col_size - 1]);
                    break;
                }

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r&&is_curr_c)
                {
                    bool is_visited = checked[curr_r][curr_c];
                    if (!is_visited)
                    {
                        Node new_node(grid[curr_r][curr_c], curr_r, curr_c);
                        bfs_queue.push(new_node);
                        //标记已访问
                        checked[curr_r][curr_c] = true;
                    }
                }
                //dir_vec
            }

            if (is_find)
            {
                break;
            }

            //while (!bfs_queue.empty())
        }

        cout << result;
        //Solution04
    }
private:
    int result = INT_MAX;
    int row_size = 0, col_size = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};


int main()
{
	{
        int row_size, col_size;
        cin >> row_size >> col_size;
        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        Solution04 solu(grid);

        return 0;
	}
	{
/*
4
50 70 20 70
*/
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
        //4 3 2 n(v_size) t(target_sum) k(target_limit)

        int v_size, target_sum, target_limit;
        cin >> v_size >> target_sum >> target_limit;

        vector<int>kind_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> kind_vec[i];
        }

        Solution02 solu(kind_vec, target_sum, target_limit);

        return 0;
	}
    vector<int>num_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream >>token)
    {
        num_vec.push_back(stoi(token));
    }

    Solution01 solu(num_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
